package com.hy.dp.bagProblem.fullBag;

public class ChangeExchange {


    /**
     * 518. 零钱兑换 II
     * 力扣题目链接
     *
     * 难度：中等
     *
     * 给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。
     *
     * 示例 1:
     *
     * 输入: amount = 5, coins = [1, 2, 5] 输出: 4 解释: 有四种方式可以凑成总金额: 5=5 5=2+2+1 5=2+1+1+1 5=1+1+1+1+1
     *
     * 示例 2: 输入: amount = 3, coins = [2] 输出: 0 解释: 只用面额2的硬币不能凑成总金额3。
     *
     * 示例 3: 输入: amount = 10, coins = [10] 输出: 1
     *
     * 思路
     * 这是一道典型的背包问题，一看到钱币数量不限，就知道这是一个完全背包。
     *
     * 但本题和纯完全背包不一样，纯完全背包是能否凑成总金额，而本题是要求凑成总金额的个数！
     *
     * 注意题目描述中是凑成总金额的硬币组合数，为什么强调是组合数呢？
     *
     * 例如示例一：
     *
     * 5 = 2 + 2 + 1
     *
     * 5 = 2 + 1 + 2
     *
     * 这是一种组合，都是 2 2 1。
     *
     * 如果问的是排列数，那么上面就是两种排列了。    组合不强调元素之间的顺序，排列强调元素之间的顺序。
     *
     * 1.确定dp数组以及下标的含义
     * dp[j]：凑成总金额j的货币组合数为dp[j]
     *
     * 2.确定递推公式
     * dp[j] （考虑coins[i]的组合总和） 就是所有的dp[j - coins[i]]（不考虑coins[i]）相加。
     *
     * 所以递推公式：dp[j] += dp[j - coins[i]];
     *
     * 这个递推公式大家应该不陌生了，我在讲解01背包题目的时候在这篇动态规划：目标和！中就讲解了，求装满背包有几种方法，一般公式都是：dp[j] += dp[j - nums[i]];
     *
     * 3.dp数组如何初始化
     * 首先dp[0]一定要为1，dp[0] = 1是 递归公式的基础。
     *
     * 从dp[i]的含义上来讲就是，凑成总金额0的货币组合数为1。
     *
     * 下标非0的dp[j]初始化为0，这样累计加dp[j - coins[i]]的时候才不会影响真正的dp[j]
     *
     * 4.确定遍历顺序
     * 本题中我们是外层for循环遍历物品（钱币），内层for遍历背包（金钱总额），还是外层for遍历背包（金钱总额），内层for循环遍历物品（钱币）呢？
     *
     * 但本题就不行了！
     *
     * 因为纯完全背包求得是能否凑成总和，和凑成总和的元素有没有顺序没关系，即：有顺序也行，没有顺序也行！
     *
     * 而本题要求凑成总和的组合数，元素之间要求没有顺序。
     *
     * 所以纯完全背包是能凑成总和就行，不用管怎么凑的。
     *
     * 本题是求凑出来的方案个数，且每个方案个数是为组合数。
     *   //1. 遍历物品  遍历背包容量
     * 假设：coins[0] = 1，coins[1] = 5。
     *
     * 那么就是先把1加入计算，然后再把5加入计算，得到的方法数量只有{1, 5}这种情况。而不会出现{5, 1}的情况。
     *
     * 所以这种遍历顺序中dp[j]里计算的是组合数！
     * //2.  遍历背包容量  遍历物品
     * 背包容量的每一个值，都是经过 1 和 5 的计算，包含了{1, 5} 和 {5, 1}两种情况。
     *
     * 此时dp[j]里算出来的就是排列数！
     * @param coins
     * @param amount
     * @return
     */
    public static int changeExchage(int [] coins,int amount){
        // 1. dp数组以及下标定义
        int [] dp = new int[amount + 1];

        // 2.推导递推式
        //dp[j]  += dp[j - coins[i]];
        // 3.初始化    //初始化dp数组，表示金额为0时只有一种情况，也就是什么都不装
        dp[0]  = 1;
        // 4.循环遍历  先遍历 物品  再 遍历 背包
        for (int i = 0; i < coins.length; i++) {
            for (int j = coins[i]; j <= amount; j++) {
                dp[j]  += dp[j - coins[i]];
            }

        }
        // 5. 结果
        return dp[amount];
    }

    public static void main(String[] args) {
        int amount = 5;
        int [] coins = {1,2,5};
        System.out.println("res: "+changeExchage(coins,amount));
    }
}
